package com.cat.dynamicPlanning;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/inverse-coin-change/
 * @create 2025/9/3 18:01
 * @since JDK17
 */

public class Solution57 {
    public List<Integer> findCoins(int[] numWays) {
        int n = numWays.length;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int w = numWays[i];
            if (dp[i + 1] == w) {   // 不用补
                continue;
            }
            if (dp[i + 1] + 1 != w) {   // 差了不只一，补不了
                return new ArrayList<>();
            }
            ans.add(i + 1);
            for (int j = i + 1; j <= n; j++) {
                dp[j] += dp[j - i - 1];
            }
        }
        return ans;
    }
}
